Full Square Rhomboids and Their Algebraic Expressions

摘要

The paper investigates relationship between algebraic expressions and graphs.We consider a digraph called a full square rhomboid that is an example ofnon-series-parallel graphs. Our intention is to simplify the expressions offull square rhomboids and eventually find their shortest representations. Withthat end in view, we describe two decomposition methods for generatingexpressions of full square rhomboids and carry out their comparative analysis.